学习同态加密：第一代全同态加密经典论文合集

全同态加密领域的首创者是Gentry，他做出的开创性工作的为三个主要的全同态加密研究阶段的铺平了道路。

本文会按照全同态加密经典论文的研究阶段进行划分，并给出相关的阅读建议。

有兴趣的同学还可以阅读往期推送，了解更多全同态加密的知识体系整理，详情请请见全同态加密知识体系整理(上)和全同态加密知识体系整理(下)。

1

第一代：基于理想格的全同态加密

经典论文

全同态加密的方法由Gentry首次提出的方案

C. Gentry, A Fully Homomorphic Encryption Scheme, vol. 20, no. 9. Stanford, CA, USA: Stanford Univ., 2009.

最初是由Smart和Vercauteren实现的，他们使用主理想格并引入了批处理技术。

N. P. Smart and F. Vercauteren, “Fully homomorphic encryption with relatively small key and ciphertext sizes,” in Proc. Int. Workshop Public Key Cryptogr. Cham, Switzerland: Springer, 2010, pp. 420–443.

该方案的批处理版本允许使用中国剩余定理(CRT)将明文向量的打包加密为单个密文。

这种技术允许同时处理多个消息。Smart-Vercauteren的实现在2011年由Gentry和Halevi[64]改进。

C. Gentry and S. Halevi, “Implementing Gentry’s fully-homomorphic encryption scheme,” in Advances in Cryptology—EUROCRYPT 2011, K. G. Paterson, Ed. Berlin, Germany: Springer, 2011, pp. 129–148.

随后，Scholl和Smart对Gentry-Halevi技术进行了改进，提供了一种适用于任何环切术领域的泛化方法。

P. Scholl and N. P. Smart, “Improved key generation for Gentry’s fully homomorphic encryption scheme,” in Proc. IMA Int. Conf. Cryptogr. Coding. Cham, Switzerland: Springer, 2011, pp. 10–22.

stehl和Steinfeld降低了刷新密文的比特复杂度(即每比特的操作数量)，并且他们的技术可以应用于不同的FHE方案，如Gentry和Smart 以及Vercauteren等人的方案。

D. Stehlé and R. Steinfeld, “Faster fully homomorphic encryption,” in Proc. Int. Conf. Theory Appl. Cryptol. Inf. Secur. Cham, Switzerland: Springer, 2010, pp. 377–394.

学习建议

此阶段文章属于早期成果，但是由于基于理想格的FHE方案的缺点是它们基于难以有效实现的数学结构，因此目前已经不再是主流方案，感兴趣可以阅读，但是研究价值与工业实现价值较低。

2

第一代：基于AGCD问题的全同态加密

经典论文

2010年，由于van Dijk等人引入了整数上的FHE方案，一种新的(比基于理想格更简单)FHE方案家族出现。

M. van Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan, “Fully homomorphic encryption over the integers,” in Advances in Cryptology—EUROCRYPT 2010, H. Gilbert, Ed. Berlin, Germany: Springer, 2010, pp. 24–43.

DGHV方案的主要缺点是计算复杂度高，公钥大小较大。

目前已经提出了几种优化和实现，具体来说，Coron等人减少了必须存储的公钥元素，这种优化只需要稍微修改一下加密过程。

J.-S. Coron, A. Mandal, D. Naccache, and M. Tibouchi, “Fully homomorphic encryption over the integers with shorter public keys,” in Advances in Cryptology—CRYPTO 2011, P. Rogaway, Ed. Berlin, Germany: Springer, 2011, pp. 487–504.

Chan和Nguyen提出了新的算法来解决AGCD问题，该算法比以前的算法快得多。

Y. Chen and P. Q. Nguyen, “Faster algorithms for approximate common divisors: Breaking fully-homomorphic-encryption challenges over the integers,” in Advances in Cryptology—EUROCRYPT 2012, D. Pointcheval and T. Johansson, Eds. Cham, Switzerland: Springer, 2012, pp. 502–519.

后来，Coron等利用模交换技术进一步减小了公钥的大小。

J.-S. Coron, D. Naccache, and M. Tibouchi, “Public key compression and modulus switching for fully homomorphic encryption over the integers,” in Advances in Cryptology—EUROCRYPT 2012, D. Pointcheval and T. Johansson, Eds. Berlin, Germany: Springer, 2012, pp. 446–464.

2013年，Kim等人和Coron等人独立提出了批处理版本的DGHV方案

J. Kim, M. S. Lee, A. Yun, and J. H. Cheon, “CRT-based fully homomorphic encryption over the integers,” Cryptol. ePrint Arch., Tech. Rep. 2013/057, 2013. [Online]. Available: https://eprint.iacr.org/2013/057

J.-S. Coron, T. Lepoint, and M. Tibouchi, “Batch fully homomorphic encryption over the integers,”

Cryptol. ePrint Arch., Tech. Rep. 2013/036, 2013. [Online]. Available: https://eprint.iacr.org/2013/036

此外，Nuida和Kurosawa提出了非二进制消息空间的批处理技术。

K. Nuida and K. Kurosawa, “(Batch) fully homomorphic encryption over integers for non-binary message spaces,” in Advances in Cryptology—EUROCRYPT 2015, E. Oswald and M. Fischlin, Eds. Berlin, Germany: Springer, 2015, pp. 537–555.

2014年，Coron等利用尺度不变性对DGHV方案进行了改进。

J.-S. Coron, T. Lepoint, and M. Tibouchi, “Scale-invariant fully homomorphic encryption over the integers,” in Proc. Int. Workshop Public Key Cryptogr. Cham, Switzerland: Springer, 2014, pp. 311–328.

2015年，Cheon和steh受到Brakerski的启发，引入了从LWE到AGCD，然后基于这种新变体提出了一种新的基于AGCD的FHE方案。

J. H. Cheon and D. Stehlé, “Fully homomorphic encryption over the integers revisited,” in Advances in Cryptology—EUROCRYPT 2015, E. Oswald and M. Fischlin, Eds. Berlin, Germany: Springer, 2015, pp. 513–536.

学习建议

目前基于AGCD的全同态加密发展比较缓慢，近年缺少里程碑性质的文章，但是在此过程中Brakerski等人提出的工作对后续的其他全同态研究带来了较大的启发，建议阅读。此外，Brakerski也是第二代全同态加密方案的杰出贡献者

Z. Brakerski, “Fully homomorphic encryption without modulus switching from classical GapSVP,” in Advances in Cryptology—CRYPTO 2012, R. Safavi-Naini and R. Canetti, Eds. Berlin, Germany: Springer, 2012, pp. 868–886.

END

往期推荐

1.文章速览 | 联邦学习 x AAAI'2023 （下）
2.深入浅出零知识证明（二）：电路模型概述3.文章速览 | 联邦学习 x AAAI'2023 （上）4.论文分享 | 基于全同态加密的跨边缘区块链网络隐私保护方案